﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TopologicalSearchAlgorithm
{
    public class TopologicalSort
    {
        public int Time = 0;
        public static TopologicalSort Instance
        {
            get
            {
                if (_instance == null)
                    _instance = new TopologicalSort();
                return _instance;
            }
        }
        public void DFS()
        {
            _SortedList.Clear();
            foreach (Node n in _nodes)
            {
                if (n.NodeColor == Color.White)
                    DFS_VISIT(n);
            }
        }
        public void DFS_VISIT(Node n)
        {
            n.NodeColor = Color.Gray;
            n.discoverTime = ++Time;
            foreach (Edge e in n.Edges)
            {
                if (e.Node2.NodeColor == Color.White)
                    DFS_VISIT(e.Node2);
            }
            n.finishTime = ++Time;
            n.NodeColor = Color.Black;
            _SortedList.AddFirst(n);
        }
        public List<Node> GetNodeList()
        {
            return _SortedList.ToList<Node>();
        }
        public void AddNode(char n)
        {
            _nodes.Add(new Node(n));
        }
        public void AddNode(Node n)
        {
            _nodes.Add(n);
        }

        public void AddEdge(char n1, char n2)
        {
            Edge e = new Edge(n1, n2);
            _edges.Add(e);
            foreach (Node n in _nodes)
            {
                if (n.Name == n1)
                    n.Edges.Add(e);
            }
        }

        public Node getNode(char _name)
        {
            foreach(Node n in _nodes)
            {
                if (n.Name == _name)
                    return n;
            }
            Node __new = new Node(_name);
            AddNode(__new);
            return __new;
        }
        private LinkedList<Node> _SortedList = new LinkedList<Node>();
        private List<Node> _nodes = new List<Node>();
        private List<Edge> _edges = new List<Edge>();
        private static TopologicalSort _instance;
    }
    public enum Color { White, Gray, Black }
    public class Node : IComparable
    {
        public Node(char n)
        {
            Name = n;
        }
        public Color NodeColor = Color.White;
        public char Name;
        public List<Edge> Edges = new List<Edge>();
        public int finishTime = 0;
        public int discoverTime = 0;

        public override string ToString()
        {
            return "Vertex: " + Name + ", Discover Time:" + discoverTime + ", Finish Time:" + finishTime;
        }
        public int CompareTo(object obj)
        {
            Node obj2 = obj as Node;
            if (obj2.finishTime > finishTime)
                return -1;// sorting lowest to highest, values are reveresed.
            else if (obj2.finishTime == finishTime)
                return 0;
            else return 1;
        }

    }
    public class Edge
    {
        public Edge(char _1, char _2)
        {
            Node1 = TopologicalSort.Instance.getNode(_1);
            Node2 = TopologicalSort.Instance.getNode(_2);
        }
        public Node Node1;
        public Node Node2;
    }
}
